package com.demo.example.hot100;

import java.util.*;

public class GroupAnagrams {
    public static void main(String[] args) {
        String[] strings=new String[]{
                "eat",
                "tea",
                "tan",
                "ate",
                "nat",
                "bat"
        };
        List<List<String>> res=groupAnagrams(strings);
        for(int i=0;i<res.size();i++){
            List<String> tmp=res.get(i);
            for(int j=0;j<tmp.size();j++){
                System.out.print(tmp.get(j)+" ");
            }
            System.out.println();
        }
    }
    public static List<List<String>> groupAnagrams(String[] strs){
        List<List<String>> res=new ArrayList<>();
        for(int i=0;i<strs.length;i++){
            String tmp=strs[i];
            //说明返回值里面目前为空
            if(res.size()==0){
                List<String> list=new ArrayList<>();
                list.add(tmp);
                res.add(list);
                continue;
            }
            //说明返回值里面不为空，我们遍历返回值内部的各个列表，看看当前字符串是否能直接添加到已有列表中
            //对于每个列表，我们不需要遍历里面的所有字符串，只需要遍历第一个即可
            boolean flag=false; //flag表示是否被当前res中包含
            for(int j=0;j<res.size();j++){
                List<String> tmpList=res.get(j); //获取字符串
                String tmpString=tmpList.get(0);
                if(isSameCharacter(tmpString,tmp)){
                    //该字符串应该属于该列表
                    tmpList.add(tmp);
                    flag=true;
                }
            }
            //说明不是，再创建一个列表
            if(!flag) {
                List<String> list = new ArrayList<>();
                list.add(tmp);
                res.add(list);
            }
        }
        return res;
    }
    //写一个方法，这个方法用于表示两个字符串包含的字符是否会相同
    public static boolean isSameCharacter(String s1,String s2){
        char[] chars1=s1.toCharArray();
        char[] chars2=s2.toCharArray();
        Arrays.sort(chars1);
        Arrays.sort(chars2);
        String string1=new String(chars1);
        String string2=new String(chars2);
        return string1.equals(string2);
    }

    public List<List<String>> groupAnagrams2(String[] strs){
        Map<String,List<String>> map=new HashMap<String,List<String>>();
        for(String str:strs){
            char[] chars=str.toCharArray();
            Arrays.sort(chars);
            String key=new String(chars);
            List<String> list=new ArrayList<>();
            if(map.containsKey(key)){
                list=map.get(key);
            }
            list.add(str);
            map.put(key,list);
        }
        return new ArrayList<List<String>>(map.values());
    }
}
